Electrical Engineering-Systems Dept.

סמינר מחלקתי

You are invited to attend a lecture by

Dr. Ido Tal

(ITA, UCSD)

on the subject:

Polar codes: construction and improved decoding

Polar codes, a class of binary error-correcting codes, have recently been invented by Arikan. Polar codes have an explicit construction and are known to be capacity achieving (for binary, memoryless, symmetric channels). Moreover, they have corresponding efficient encoding and decoding algorithms. To date, no other family of codes is known to possess all of these favorable traits.

Although polar codes are explicitly defined, a straightforward construction is intractable. In the first part of the talk we present a method by which polar codes can be efficiently constructed. The key observation is that a channel with a large output alphabet size can be "sandwiched" between two channels with a smaller output alphabet size. 

Once polar codes were constructed, it quickly became apparent that their performance under Arikan's successive cancellation decoding scheme is inferior to that of the current state-of-the-art LDPC codes. In the second part of the talk we present an improved decoder for polar codes. Our decoder employs list decoding at an intermediate stage, but ultimately puts out a single codeword. The complexity of decoding is O(L n  log n), where L is the list size and n is the codeword length. We then introduce a slightly modified family of polar codes. Decoding the modified family of polar codes with our improved decoder results in performance comparable with the current state-of-the-art.

Short bio:

Ido Tal got his B.Sc., M.Sc., and Ph.D. from the Computer Science Department, Technion, Israel. His M.Sc. was done under Prof. Ronny Roth. His Ph.D. was done under Prof. Tuvi Etzion and Prof. Ronny Roth. Ido is currently an ITA postdoc at UCSD, working with Prof. Alexander Vardy. Ido's research interests are coding theory in general, polar codes, multidimensional constraints, and list decoding. He is the recipient of the Hewlett-Packard Excellence Fellowship for Technion Ph.D. Students.